package com.wfm.leetcode.editor.cn;

/**
 * 交错字符串
 * 2025-03-03 11:31:57
 * 我们定义 f(i,j) 表示 s1的前 i 个元素和 s2的前 j 个元素是否能交错组成 s3的前 i+j 个元素
 * 时间复杂度：O(n*m)
 * 空间复杂度：O(n*m)
 * 可以考虑用滚动数组优化，但是这里没写
 */
class InterleavingString {

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();

        if (n + m != t) {
            return false;
        }

        boolean[][] f = new boolean[n + 1][m + 1];

        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    // 为啥要一个||操作，是因为，假设dp的值通过s1计算完成之后变成了True，但是通过s2之后又变成了false，
                    // 这样会对后面的运算产生影响，因此需要||操作
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }

        return f[n][m];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new InterleavingString().new Solution();
        
    }
}